//买卖股票的最佳时机含冷冻期
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        //dp状态表示：第i天结束以后，我们所处的状态，此时的最大利润
        //dp[i][0] = 买入，dp[i][1] = 可交易 ， dp[i][2] = 冷冻期 
        int n = prices.size();
        vector<vector<int>> dp( n , vector<int>(3));
        //买入 => 买入 = 啥也不干 ， dp[i][0] = dp[i-1][0]
        //冷冻期 ≠> 买入：第i天无法交易。
        //可交易 => 买入 = 第i天把股票买了
        //dp[i][0] = max(dp[i-1][0],dp[i-1][1]-prices[i])

        //买入 => 冷冻期 = 第i天把股票卖了
        //可交易 => 冷冻期 = 第i天把股票卖了
        //冷冻期 ≠> 冷冻期

        //买入 ≠> 可交易
        //可交易 => 可交易：第i天啥也不干
        //冷冻期 => 可交易
        dp[0][0] = prices[0]*(-1);
        for(size_t i = 1 ; i < n ; ++i)
        {
            for(size_t j = 0 ; j < 3 ; ++j)
            {
                if(j == 0)
                {
                    //当天处于买入状态
                    dp[i][0] = max(dp[i-1][0],dp[i-1][1]-prices[i]);
                }
                else if(j == 1)
                {
                    //当天处于可交易状态
                    dp[i][1] = max(dp[i-1][1],dp[i-1][2]);
                }
                else 
                {
                    //当天处于冷冻状态
                    dp[i][2] = dp[i-1][0] + prices[i];
                }
            }
        }
        int max = INT_MIN;
        for(size_t i = 0 ; i < 3 ; ++i)
        {
            if(dp[n-1][i] > max)
                max = dp[n-1][i];
        }
        return max;
    }
};

//买卖股票的最佳时期含手续费
class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        int n = prices.size();
        vector<vector<int>> dp(n,vector<int>(2));
        //dp[i]表示第i天结束之后，此时的最大利润。可以细化为f[i]和g[i]
        //f[i]表示第i-1天结束，第i天选择买入时的最大利润
        //g[i]表示第i-1天结束，第i天选择卖出时的最大利润
        //f[i] = max(g[i-1]-prices[i],f[i-1]);
        //g[i] = max(g[i-1],f[i-1]-fee+prices[i]);
        dp[0][0] = prices[0]*(-1);
        dp[0][1] = 0;
        for(size_t i = 1 ; i < n ; ++i)
        {
            for(size_t j = 0 ; j < 2 ; ++j)
            {
                if(j == 0)
                {
                    //当天处于买入状态
                    dp[i][0] = max(dp[i-1][1]-prices[i],dp[i-1][0]);
                }
                else 
                {
                    //当天处于卖出状态
                    dp[i][1] = max(dp[i-1][1],dp[i-1][0]+prices[i]-fee);
                }
            }
        }
        return max(dp[n-1][0],dp[n-1][1]);
    }
};

//买卖股票的最佳实际III
#define MAX 0x3f3f3f3f
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        vector<vector<int>> f(n,vector<int>(3,-MAX));
        auto g = f;
        //f[i][j]：第i天结束以后，处于"买入"，已经完成了j次交易，此时的最大利润(买入不会使得交易次数变多)
        //g[i][j]：第i天结束以后，处于"卖出"，已经完成了j次交易，此时的最大利润(从买入到卖出会使交易次数变多)
        f[0][0] = -prices[0];
        g[0][0] = 0;

        for(size_t i = 1 ; i < n ; ++i)
        {

            for(size_t j = 0 ; j < 3 ; ++j)
            {

                f[i][j] = max(f[i-1][j],g[i-1][j]-prices[i]);
                g[i][j] = g[i-1][j];
                if(j>=1)
                {
                    g[i][j] = max(g[i-1][j],f[i-1][j-1]+prices[i]);
                }
            }
        }
        int max = -MAX;
        for(size_t i = 0 ; i < 3 ; ++i)
        {
            if(g[n-1][i] > max)
                max = g[n-1][i];
        }
        return max;
    }
};

//买卖股票的最佳实际IV
class Solution {
public:
    const int MAX = 0x3f3f3f3f;
    int maxProfit(int k, vector<int>& prices) {
        int n = prices.size();
        vector<vector<int>> f(n,vector<int>(k+1,-MAX));
        auto g = f;
        f[0][0] = -prices[0];
        g[0][0] = 0;
        for(size_t i = 1 ; i < n ; ++i)
        {
            for(size_t j = 0 ; j <= k ; ++j)
            {
                f[i][j] = max(f[i-1][j],g[i-1][j]-prices[i]);
                g[i][j] = g[i-1][j];
                if(j >= 1 && g[i-1][j] < (f[i-1][j-1] + prices[i]))
                {
                    g[i][j] = f[i-1][j-1] + prices[i];
                }
            }
        }
        int retMax = -MAX;
        for(size_t i = 0 ; i <= k ; ++i)
        {
            if(g[n-1][i] > retMax)
                retMax = g[n-1][i];
        }
        return retMax;
    }
};